iT邦幫忙

第 11 屆 iThome 鐵人賽

DAY 5
2
Software Development

使用JavaScript學習資料結構與演算法系列 第 5

Day5-陣列(Array)和鏈結串列(Linked List)的比較

  • 分享至 

  • xImage
  •  

在學習完陣列和鏈結串列之後呢,我們來把它們做統整比較吧!不過首先要先介紹一個網站,裡面整理了各式資料結構的時間複雜度並整理成表格。網站連結如下:

https://www.bigocheatsheet.com/

此圖片是網站的畫面截圖:

接著我們就要去分析陣列和鏈結串列的時間複雜度,做優缺點的分析:

Array

優點:

  1. 存取只需要 O(1) 時間對 Array 的資料做存取。
  2. 比 Linked list 為節省記憶體空間,因為 linked list 需要多一個指標 pointer 來記錄下一個節點的記憶體位置。

缺點:

  1. 新增/刪除資料比較麻煩,若要在第一個位置新增資料,就需要把矩陣中所有元素往後移動,並且是O(N)的時間複雜度。同理,若要刪除第一個位置的資料,也需要 O(N) 的時間複雜度把矩陣中剩餘的元素往前移動。
  2. 若時常在新增資料,要時常調整陣列的大小,會花費 O(N) 的時間在搬動資料(把資料從舊的陣列移動到新的陣列)。(ex: unshift() 函式,從前面加入陣列元素會把原本元素都往後推,O(n))

適用時機:

  1. 快速存取資料時
  2. 已知資料的數量,如此便不用經常改變陣列大小
  3. 要求記憶體空間的使用越少越好。

Linked list

優點:

  1. 新增/刪除資料比 Array 簡單,只要對要新增刪除的相關節點們調整指標即可,不需要像 Array 搬動其餘元素。
  2. linked list 的資料數量能動態的向記憶體要空間或釋放空間,不像 Array 會有 "重新定義陣列大小" 的問題。

缺點:

  1. 因為 linked list 不能直接透過索引值找到某節點(ex: 像陣列可以透過 array[index] 找到要的元素),若要找到特定節點,需要從頭開始找起,搜尋的時間複雜度為 O(N)。
  2. 需要額外的記憶體空間來儲存指標。

Linked List 時間複雜度整理

  • 插入節點: 開頭節點插入 O(1) or 其他位置 O(n)
  • 刪除: 開頭節點刪除 O(1) or 其他位置 O(n)
  • 搜尋: O(n)
  • 取得: O(n)

適用時機:

  1. 無法預期資料數量或頻繁變動資料數量時。
  2. 需要頻繁地新增/刪除資料時。
  3. 不需要快速查詢資料。

以上內容就是陣列和鏈結串列的比較,明天我們將來學習堆疊!


上一篇
Day4-來了解鏈結串列(Linked List)並實作它吧!
下一篇
Day6-來了解堆疊並實作它吧!
系列文
使用JavaScript學習資料結構與演算法30
圖片
  直播研討會
圖片
{{ item.channelVendor }} {{ item.webinarstarted }} |
{{ formatDate(item.duration) }}
直播中

1 則留言

0
whitefloor
iT邦研究生 2 級 ‧ 2021-07-30 18:54:56

那串網站演算法比較超棒

harry xie iT邦研究生 1 級 ‧ 2021-07-30 19:33:26 檢舉

對啊哈哈

我要留言

立即登入留言